package com.squirrel.michale;

import java.util.ArrayDeque;
import java.util.Deque;

public class Day20250103_LeetCode002865 {

    public long maximumSumOfHeights(int[] heights) {
        int n = heights.length;
        long res = 0;
        for (int i = 0; i < n; i++) {
            int pre = heights[i];
            long sum = pre;
            for (int j = i - 1; j >= 0; j--) {
                pre = Math.min(pre, heights[j]);
                sum += pre;
            }
            int suf = heights[i];
            for (int j = i + 1; j < n; j++) {
                suf = Math.min(suf, heights[j]);
                sum += suf;
            }
            res = Math.max(res, sum);
        }
        return res;
    }


    public long maximumSumOfHeights02(int[] heights) {
        int n = heights.length;
        long res = 0;
        long[] prefixSum = new long[n];
        long[] suffixSum = new long[n];
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();

        for (int i = 0; i < n; i++) {
            while (!stack1.isEmpty() && heights[i] < heights[stack1.peek()]) {
                stack1.pop();
            }
            if (stack1.isEmpty()) {
                prefixSum[i] = (long) (i + 1) * heights[i];
            } else {
                prefixSum[i] = prefixSum[stack1.peek()] + (long) (i - stack1.peek()) * heights[i];
            }
            stack1.push(i);
        }
        for (int i = n - 1; i >= 0; i--) {
            while (!stack2.isEmpty() && heights[i] < heights[stack2.peek()]) {
                stack2.pop();
            }
            if (stack2.isEmpty()) {
                suffixSum[i] = (long) (n - i) * heights[i];
            } else {
                suffixSum[i] = suffixSum[stack2.peek()] + (long) (stack2.peek() - i) * heights[i];
            }
            stack2.push(i);
            res = Math.max(res, prefixSum[i] + suffixSum[i] - heights[i]);
        }
        return res;
    }
}
